图
图中顶点的度：与该顶点相连的边的数量。
在无向图中，一个顶点的度数就是和该顶点相连的边的数量。
在有向图中，一个顶点的度数等于该顶点的入度和出度的和。（入度是指指向该顶点的边的数量，出度是从该顶点出发的边的数量。）
二叉树公式推导(等比数列求和):
f(k)=20+21+22+...+2(k−1)2∗f(k)=21+22+23+...+2k2∗f(k)−f(k)=2k−20\begin{aligned} f(k) = 2^0 + 2^1 + 2^2 +...+2^{(k-1)} \\ 2*f(k) = 2^1 + 2^2 + 2^3 +...+2^k\\ 2*f(k)-f(k)= 2^k -2^0 \end{aligned}f(k)=20+21+22+...+2(k−1)2∗f(k)=21+22+23+...+2k2∗f(k)−f(k)=2k−20
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
2叉树公式:f(k)=2k−20a叉树公式:f(a)=(ak−1)/(a−1);注意：节点不一定是个值\begin{aligned} 2叉树公式:f(k) = 2^k -2^0 \\ a叉树公式:f(a)=(a^k-1)/(a-1);\\ 注意：节点不一定是个值 \\ \end{aligned}2叉树公式:f(k)=2k−20a叉树公式:f(a)=(ak−1)/(a−1);注意：节点不一定是个值
二叉树的性质
3. 性质3：对任意一个二叉树，如果其叶子结点的数量为n0n_0n0 ，度为2的结点数为n2n_2n2 ，则一定满足n0=n2+1n_0=n_2+1n0 =n2 +1.
4. 具有n(n>=0)个结点的完全二叉树的深度为⌊log2n+1⌋\large具有n(n>=0)个结点的完全二叉树的深度为\lfloor log_2n+1\rfloor具有n(n>=0)个结点的完全二叉树的深度为⌊log2 n+1⌋
5. 如将一棵有n个节点的完全二叉树自顶向下，同一层自左向右连续给结点编号1,2,……,n\color{red}{1,2,……,n}1,2,……,n;
1. 若i=1,则结点i为根，无父结点
2. 若i>1,则i的父节点编号为⌊i/2⌋\color{green}{ \lfloor i/2 \rfloor}⌊i/2⌋
3. 若2*i>n,则i无左孩子，否则其左孩子编号为2∗i2*i2∗i.
4. 若2*i+1>n,则i无右孩子，负责其有孩子编号为2×i+12 \times i+12×i+1.
存储方法
带权图
map[x][y]表示结点x到结点y边的权值。在边不存在的情况下，会适当地取较大的常数，与普通权值进行区分。
无向图+不带权值图示
无向图+带权值表示
有向图+不带权值表示
有向图+带权值表示
树
先序队（根左右)
* 先序队列也叫前序队列、先根队列、可记作根左右（二叉树父结点向下先左后右）
中序遍历（左根右）
后序遍历（左右根）
二叉树重建
|A\B|前序队列|中序队列|后序队列|
|:--:|:--:|:--:|
|前序队列|0|1|0|
|中序队列|1|0|1|
|后序队列|0|1|0|
故重构必有中序对列
动态规划(DP)(DP)(DP)
* 是一种思想
* 不存在一种万能的思想
1.划分阶段
* 数列每一项：iii
2.确定状态
* 状态：f[i]f[i]f[i]
3.确定决策并写出状态转移方程式
* 例如：f[i]=f[i−1]+1f[i]=f[i-1]+1f[i]=f[i−1]+1
*
【例题】 最大子段和
题目描述
给出一个长度为 nnn 的序列 aaa，选出其中连续且非空的一段使得这段和最大。
输入格式
第一行是一个整数，表示序列的长度 nnn。
第二行有 nnn 个整数，第 iii 个整数表示序列的第 iii 个数字 aia_iai 。
输出格式
输出一行一个整数表示答案。
样例 #1
样例输入 #1
样例输出 #1
提示
样例 1 解释
选取 [3,5][3, 5][3,5] 子段 {3,−1,2}\{3, -1, 2\}{3,−1,2}，其和为 444。
数据规模与约定
* 对于 40%40\%40% 的数据，保证 n≤2×103n \leq 2 \times 10^3n≤2×103。
* 对于 100%100\%100% 的数据，保证 1≤n≤2×1051 \leq n \leq 2 \times 10^51≤n≤2×105，−104≤ai≤104-10^4 \leq a_i \leq 10^4−104≤ai ≤104。
【参考代码】
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
1. 最优化原理：（最优子结构）:
* 如果问题的最优解所包含的子问题的解也是最优的\color{red}{\large\textbf{最优解所包含的子问题的解也是最优的}}最优解所包含的子问题的解也是最优的,就称该问题具有最优子结构，即满足该原理。
2. 无后效性：
* 即某阶段状态 一旦确定\color{red}{\large\textbf{ 一旦确定}} 一旦确定，就 不受这个状态以后的影响\color{red}{\large\textbf{ 不受这个状态以后的影响}} 不受这个状态以后的影响.也就是说，某状态以后的过程不会影响以前的状态，只与当前状态有关\color{red}{\large\textbf{只与当前状态有关}}只与当前状态有关.
3. 子问题重叠：
* 即 子问题之间是不独立的\color{red}{\large\textbf{子问题之间是不独立的}}子问题之间是不独立的,一个子问题在下一阶段决策中可能被多次使用到\color{red}{\large\textbf{可能被多次使用到}}可能被多次使用到.（该性质并不是动态规划适用的必要条件\color{red}{\large\textbf{并不是动态规划适用的必要条件}}并不是动态规划适用的必要条件,但是如果没有这条性质，动态规划算法同其他算法相比就不具备优势\color{red}{\large\textbf{不具备优势}}不具备优势）
